#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_NODES_NR 16
#define key(A) (A) // wyznaczony klucz
#define less(A, B) (A < B) // porownywanie kluczy
#define eq(A, B) (!less(A, B) && !less(B, A))

typedef char info; // struktura elementu
typedef struct node* link; // dowiazanie
struct node { // struktura wezla
  info item; 
  link l, r; 
  int N; 
};
link head, z;
link NEW(info , link , link , int ); // nowy wezel
int inr; // liczba elementow
info nullItem; // element pusty

info *st; // tablica symboli
static int N; // liczba wezlow w tablicy symboli (ts)
void st_init(); // inicjowanie ts
info searchR(link , char );
void st_insert(info ); // wstawianie do ts
info st_search(char ); // wyszukiwanie wezla o podanym kluczu w ts
link insertR(link , info );
void st_show();

int main()
{ 
  int i;
  int nnr;
  info nodestab[MAX_NODES_NR];
  nullItem = '0';
  strcpy(nodestab, "ABCDEFGHI");
  nnr = strlen(nodestab);
  st_init(); // inicjowanie tablicy symboli
  for(i = 0; i < nnr; i++) // loop for insertion 
    st_insert(nodestab[i]);
  st_show(); // wydruk
  return 0;
}

link NEW(info item, link l, link r, int N)
{ 
  link x = malloc(sizeof *x); 
  x->item = item; x->l = l; x->r = r; x->N = N;
  return x;
}

void st_init()
{ 
  head = (z = NEW(nullItem, 0, 0, 0)); 
}

info searchR(link h, char v)
{ 
  char t = key(h->item);
  if (h == z) 
    return nullItem;
  if eq(v, t) 
	 return h->item;
  if less(v, t) 
	   return searchR(h->l, v);
  else 
    return searchR(h->r, v);
}

info st_search(char v) 
{ 
  return searchR(head, v); 
} 

link rotR(link h)
{ 
  link x = h->l; 
  h->l = x->r; 
  x->r = h; 
  return x; 
}

link rotL(link h)
{ 
  link x = h->r; 
  h->r = x->l; 
  x->l = h; 
  return x; 
}

link insertT(link h, info item)
{ 
  char v = key(item);
  if (h == z) 
    return NEW(item, z, z, 1); 
  if (less(v, key(h->item))) { 
    h->l = insertT(h->l, item); 
    h = rotR(h); 
  }
  else { 
    h->r = insertT(h->r, item); 
    h = rotL(h); 
  }
  return h;
}

link insertR(link h, info item)
{ 
  char v = key(item), t = key(h->item);
  if (h == z) 
    return NEW(item, z, z, 1);
  if (rand()< RAND_MAX/(h->N+1)) 
    return insertT(h, item);
  if less(v, t) h->l = insertR(h->l, item);
  else 
    h->r = insertR(h->r, item);
  (h->N)++; 
  return h;
}

void st_insert(info item)
{ 
  head = insertR(head, item); 
}

void showR(link h)
{
  if (h == NULL)
    return;
  showR(h->l);
  if (h->item != nullItem)
    printf("%c ", h->item);
  showR(h->r);
}

void st_show()
{
  showR(head);
  printf("\n");
}
